package internal.insertion;

/**
 * @描述：直接插入排序
 * @思想：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
 * @要点：设立哨兵，作为临时存储和判断数组边界之用。
 * @适用场合：插入排序是把序列中的值插入一个已经排序好的序列中，直到该序列的结束。它比冒泡排序快2倍。一般不适合数据量比较大的场合或数据重复比较多的场合。
 * @效率：时间复杂度：O（n^2）；稳定排序
 * @作者：hongxingfan
 * @时间：2014年9月4日 下午5:31:46
 */
public class DirectInsertionSort {

    public static void main(String[] args) {
        int[] datas = { 9, 4, 1, 8, 7, 5, 2, 0, 3, 4, 6 };

        directInsertionSort(datas);

        // 结果输出
        for (int data : datas)
            System.out.print(data + " ");
        System.out.println();
    }

    // 要点：第一次遍历的索引是1，内循环从后往前开始
    public static void directInsertionSort(int[] datas) {
        for (int i = 1; i < datas.length; i++) {
            int tmp = datas[i]; // 把i对应的值拿出来往前比较
            int j = i - 1;
            // 核心就是指针的移动
            while (j >= 0) {
                if (datas[j] > tmp) {
                    datas[j + 1] = datas[j]; // 最坏(n*(n-1))/2次交换
                    j--;
                } else
                    break;
            }
            datas[j + 1] = tmp; // 由于每次j--；所以最后+1补偿
        }
    }
}
